package com.lei.leetcode;

/**
 * @Author LeiXiaoLei
 * @Date 2022/8/13 20:43
 * @Version 1.0
 */
public class S_1011 {
    public int shipWithinDays(int[] weights, int days) {
        int l = getMaxValue(weights), r = sum(weights);
        while (r > l) {
            int mid = l + (r - l) / 2;
            if (days(weights, mid) <= days) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    private int days(int[] weights, int k) {
        int cur = 0, res = 0;
        for (int weight : weights)
            if (cur + weight <= k) cur += weight;
            else {
                res++;
                cur = weight;
            }
        res++;
        return res;
    }

    private int getMaxValue(int[] arr) {
        int res = arr[0];
        for (int i = 1; i < arr.length; i++)
            if (arr[i] > res) res = arr[i];
        return res;
    }

    private int sum(int[] arr) {
        int res = 0;
        for (int j : arr) res += j;
        return res;
    }
}
